package baseclass.a_sort.mergeSort;


import baseclass.a_sort.ArraysTool;

/**
 * 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。
 * <p>
 * 求一个数组的小数和
 * 例子：
 * [1,3,4,2,5]
 * 1左边比1小的数， 没有；
 * 3左边比3小的数， 1；
 * 4左边比4小的数， 1、 3；
 * 2左边比2小的数， 1；
 * 5左边比5小的数， 1、 3、 4、 2；
 * 所以小和为1+1+3+1+1+3+4+2=16
 *
 * @date 2020/2/26 19:42
 */
public class SmallNum_小数和 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 5};
        System.out.println("方式1:O(N²)");
        System.out.println(solution(arr));
        System.out.println("方式2：O(NlogN)");
        int result = getSmallSum(arr);
        System.out.println(result);

    }
    //方式1：暴力
    public static int solution(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        int sum = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                sum += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return sum;
    }

    public static int getSmallSum(int[] arr) {
        if (!ArraysTool.check(arr)) return 0;
        return process(arr, 0, arr.length - 1);
    }


    private static int process(int[] arr, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        return process(arr, l, mid)
                + process(arr, mid + 1, r)
                + doMerge(arr, l, mid, r);
    }

    private static int doMerge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int res = 0;
        int p1 = l;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= r) {
            //p2 到 r有序,小于则比p2后面的都小
            if (arr[p1] < arr[p2]) {
                res += arr[p1] * (r - p2 + 1);
            }
            help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= r) {
            help[index++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }
}
